In computing, a cache is a block of memory used for temporary storage of frequently accessed data, and allows future requests for cached data to be more quickly serviced than requests for non-cached data. If requested data is contained in the cache (a scenario known as a “cache hit”), the request can be served by simply reading the cache, which is comparably faster than accessing the data from main memory. Conversely, if the requested data is not contained in the cache (a scenario known as a “cache miss”), the data is recomputed or, in conventional techniques, filled into the cache from its original storage location, which is slower than simply reading the data from the cache. Overall system performance is thus improved, in terms of speed, when a larger portion of data requests are serviced from cache memory.
Since cache memory is typically smaller than main memory, data previously filled into the cache may need to be replaced by data used more recently. To do so, cache replacement algorithms are employed. Conventional cache replacement algorithms include least recently used (LRU) algorithms, most recently used (MRU) algorithms, least frequently used (LFU) algorithms, random replacement algorithms, and so on. Broadly speaking, cache replacement algorithms are a set of optimizing instructions that a computer program or a hardware-maintained structure implements for managing the cache memory. In particular, cache replacement algorithms select which information in the cache memory to evict in order to make room for information from main memory.
Many of the conventional cache replacement algorithms do not maintain information about data blocks that are not currently in cache memory. As a result, when a size of a working set of data exceeds a size of the cache memory, excessive fill and eviction traffic can be generated. This excessive fill and eviction traffic can cause a condition known as “thrashing”, in which a number of cache misses increases dramatically and time spent performing cache fill and eviction as a result of the misses can surpass the time spent performing the originally requested computing operations for the working set of data. Accordingly, conventional cache replacement algorithms have drawbacks which are capable of hampering computing operations.